package gailv.lasiweijiasi;
import java.util.Random;

public class VegasEightQueens {

    private static final int SIZE = 8;
    private static final Random random = new Random();
    private int[] board; // 存储皇后列位置的数组

    public VegasEightQueens() {
        board = new int[SIZE];
    }

    public boolean solve() {
        while (true) {
            if (placeQueensRandomly(0)) {
                printSolution();
                return true;
            }
            // 如果找不到解决方案，将board重置并重新尝试
            for (int i = 0; i < SIZE; i++) {
                board[i] = 0;
            }
        }
    }

    private boolean placeQueensRandomly(int row) {
        if (row == SIZE) {
            return true; // 所有皇后都放置完毕
        }
        for (int tries = 0; tries < SIZE; tries++) {
            int col = random.nextInt(SIZE); // 随机选择列
            if (isSafe(row, col)) {
                board[row] = col; // 放置皇后
                if (placeQueensRandomly(row + 1)) {
                    return true;
                }
                // 回溯
                board[row] = -1;
            }
        }
        // 如果这一行没有找到合适的位置，则重新开始
        return false;
    }

    private boolean isSafe(int row, int col) {
        for (int i = 0; i < row; i++) {
            // 检查列和对角线是否冲突
            if (board[i] == col ||
                    Math.abs(board[i] - col) == row - i ||
                    board[i] - col == row - i ||
                    board[i] - col == i - row) {
                return false;
            }
        }
        return true;
    }

    private void printSolution() {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (board[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        VegasEightQueens vegasQueens = new VegasEightQueens();
        if (vegasQueens.solve()) {
            System.out.println("找到解");
        } else {
            System.out.println("无解");
        }
    }
}